package com.github.hgkmail.hello.leetcode101.greedy;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/candy
 */
public class LC135Candy {
    public int candy(int[] ratings) {
        //bases case
        if (ratings.length<=0) {
            return 0;
        }
        if (ratings.length==1) {
            return 1;
        }
        //初始化，至少一个糖果
        int[] candy = new int[ratings.length];
        for (int i = 0; i < ratings.length; i++) {
            candy[i]=1;
        }
        //从左向右
        for (int i = 0; i < ratings.length-1; i++) {
            if (ratings[i]<ratings[i+1]) {
                candy[i+1]=candy[i]+1;
            }
        }
        //从右向左
        for (int i = ratings.length-1; i > 0; i--) {
            if (ratings[i]<ratings[i-1]) {
                candy[i-1]=Math.max(candy[i-1], candy[i]+1); //注意，这里取max
            }
        }
        return Arrays.stream(candy).sum();
    }

    public static void main(String[] args) {
        int res = new LC135Candy().candy(new int[]{1,3,2,2,1});
        System.out.println(res);
    }

}
